package 代码随想录_回溯.数独;

/**
 * @author zx
 * @create 2022-08-12 14:08
 */
public class 解数独_37 {
    /**
     * 递归的下一层的棋盘一定比上一层的棋盘多一个数,等数填满了棋盘自然就终止(填满当然好了,说明找到结果了)
     * 所以不需要终止条件！
     *
     * 注意return false:
     * 如果一行一列确定下来, 尝试了9个数都不行,说明这个棋盘找不到解决数独问题的解！
     * 那么会直接返回, 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
     *
     * 注意这道题和36的isValid()中关于board[][]中的填写,不同;是个大坑！！！
     */
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
    private boolean dfs(char[][] board){
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] != '.'){
                    continue;
                }
                for(char k = '1';k <= '9';k++){//(i, j)这个位置放k是否合适
                    if(isValid(board,i,j,k)){
                        board[i][j] = k;//放置k
                        if(dfs(board)) return true;//如果找到合适一组立刻返回
                        board[i][j] = '.';// 回溯, 撤销k
                    }
                }
                return false;//9个数都试完了,都不行,那么就返回false
            }
        }
        return true;//遍历完没有返回false, 说明找到了合适棋盘位置
    }
    private boolean isValid(char[][] board, int row, int col, char val){
        //判断行
        for(int i = 0;i < 9;i++){
            if(board[row][i] == val){
                return false;
            }
        }
        //判断列
        for(int i = 0;i < 9;i++){
            if(board[i][col] == val){
                return false;
            }
        }
        //判断九宫格
        int heng = (row / 3) * 3;
        int zong = (col / 3) * 3;
        for(int i = heng;i < heng + 3;i++){
            for(int j = zong;j < zong + 3;j++){
                if(board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}
